#include "main/utils.h"
using namespace std;

int minCost(const vector<vector<int>> cost) {
  vector<vector<int>> dp = {{cost[0][0], cost[0][1], cost[0][2]}};
  for (int i = 1; i < cost.size(); ++i) {
    vector<int> tmp;
    tmp.push_back(min(dp[i - 1][1], dp[i - 1][2]) + cost[i][0]);
    tmp.push_back(min(dp[i - 1][0], dp[i - 1][2]) + cost[i][1]);
    tmp.push_back(min(dp[i - 1][0], dp[i - 1][1]) + cost[i][2]);
    dp.push_back(tmp);
  }
  int min_tmp = min(dp.back()[0], dp.back()[1]);
  min_tmp = min(min_tmp, dp.back()[2]);
  return min_tmp;
}

int minCost1(const vector<vector<int>> cost) {
  int length = cost.size();
  int dp[2][3] = {{cost[0][0], cost[0][1], cost[0][2]}};
  for (int i = 1; i < length; ++i) {
    dp[i % 2][0] = min(dp[(i - 1) % 2][1], dp[(i - 1) % 2][2]) + cost[i][0];
    dp[i % 2][1] = min(dp[(i - 1) % 2][0], dp[(i - 1) % 2][2]) + cost[i][1];
    dp[i % 2][2] = min(dp[(i - 1) % 2][0], dp[(i - 1) % 2][1]) + cost[i][2];
  }
  int min_tmp = min(dp[(length - 1) % 2][0], dp[(length - 1) % 2][1]);
  min_tmp = min(min_tmp, dp[(length - 1) % 2][2]);
  return min_tmp;
}

int main() {
  vector<vector<int>> cost = {{17, 2, 16}, {15, 14, 5}, {13, 3, 1}};
  cout << minCost(cost) << endl;
  cout << minCost1(cost) << endl;

  return 0;
}
